1. Field
The present systems, methods and articles are generally related to the use of analog processors, for example quantum processors, and are related to the use of relational databases with such processors.
2. Description of the Related Art
A Turing machine is a theoretical computing system, described in 1936 by Alan Turing. A Turing machine that can efficiently simulate any other Turing machine is called a Universal Turing Machine (UTM). The Church-Turing thesis states that any practical computing model has either the equivalent or a subset of the capabilities of a UTM.
A quantum computer is any physical system that harnesses one or more quantum effects to perform a computation. A quantum computer that can efficiently simulate any other quantum computer is called a Universal Quantum Computer (UQC).
In 1981 Richard P. Feynman proposed that quantum computers could be used to solve certain computational problems more efficiently than a UTM and therefore invalidate the Church-Turing thesis. See e.g., Feynman R. P., “Simulating Physics with Computers”, International Journal of Theoretical Physics, Vol. 21 (1982) pp. 467-488. For example, Feynman noted that a quantum computer could be used to simulate certain other quantum systems, allowing exponentially faster calculation of certain properties of the simulated quantum system than is possible using a UTM.
Approaches to Quantum Computation
There are several general approaches to the design and operation of quantum computers. One such approach is the “circuit model” of quantum computation. In this approach, qubits are acted upon by sequences of logical gates that are the compiled representation of an algorithm. Circuit model quantum computers have several serious barriers to practical implementation. In the circuit model, it is required that qubits remain coherent over time periods much longer than the single-gate time. This requirement arises because circuit model quantum computers require operations that are collectively called quantum error correction in order to operate. Quantum error correction cannot be performed without the circuit model quantum computer's qubits being capable of maintaining quantum coherence over time periods on the order of 1,000 times the single-gate time. Much research has been focused on developing qubits with coherence sufficient to form the basic information units of circuit model quantum computers. See e.g., Shor, P. W. “Introduction to Quantum Algorithms”, arXiv.org:quant-ph/0005003 (2001), pp. 1-27. The art is still hampered by an inability to increase the coherence of qubits to acceptable levels for designing and operating practical circuit model quantum computers.
Another approach to quantum computation, involves using the natural physical evolution of a system of coupled quantum systems as a computational system. This approach does not make critical use of quantum gates and circuits. Instead, starting from a known initial Hamiltonian, it relies upon the guided physical evolution of a system of coupled quantum systems wherein the problem to be solved has been encoded in the terms of the system's Hamiltonian, so that the final state of the system of coupled quantum systems contains information relating to the answer to the problem to be solved. This approach does not require long qubit coherence times. Examples of this type of approach include adiabatic quantum computation, cluster-state quantum computation, one-way quantum computation, quantum annealing and classical annealing, and are described, for example, in Farhi, E. et al, “Quantum Adiabatic Evolution Algorithms versus Stimulated Annealing” arXiv.org:quant-ph/0201031 (2002), pp 1-24.
Qubits
As mentioned previously, qubits can be used as fundamental units of information for a quantum computer. As with bits in UTMs, qubits can refer to at least two distinct quantities; a qubit can refer to the actual physical device in which information is stored, and it can also refer to the unit of information itself, abstracted away from its physical device.
Qubits generalize the concept of a classical digital bit. A classical information storage device can encode two discrete states, typically labeled “0” and “1”. Physically these two discrete states are represented by two different and distinguishable physical states of the classical information storage device, such as direction or magnitude of magnetic field, current, or voltage, where the quantity encoding the bit state behaves according to the laws of classical physics. A qubit also contains two discrete physical states, which can also be labeled “0” and “1”. Physically these two discrete states are represented by two different and distinguishable physical states of the quantum information storage device, such as direction or magnitude of magnetic field, current, or voltage, where the quantity encoding the bit state behaves according to the laws of quantum physics. If the physical quantity that stores these states behaves quantum mechanically, the device can additionally be placed in a superposition of 0 and 1. That is, the qubit can exist in both a “0” and “1” state at the same time, and so can perform a computation on both states simultaneously. In general, N qubits can be in a superposition of 2N states. Quantum algorithms make use of the superposition property to speed up some computations.
In standard notation, the basis states of a qubit are referred to as the |0 and |1 states. During quantum computation, the state of a qubit, in general, is a superposition of basis states so that the qubit has a nonzero probability of occupying the |0 basis state and a simultaneous nonzero probability of occupying the |1 basis state. Mathematically, a superposition of basis states means that the overall state of the qubit, which is denoted |Ψ, has the form |Ψ=a|0+b|1, where a and b are coefficients corresponding to the probabilities |a|2 and |b|2, respectively. The coefficients a and b each have real and imaginary components, which allows the phase of the qubit to be characterized. The quantum nature of a qubit is largely derived from its ability to exist in a coherent superposition of basis states and for the state of the qubit to have a phase. A qubit will retain this ability to exist as a coherent superposition of basis states when the qubit is sufficiently isolated from sources of decoherence.
To complete a computation using a qubit, the state of the qubit is measured (i.e., read out). Typically, when a measurement of the qubit is performed, the quantum nature of the qubit is temporarily lost and the superposition of basis states collapses to either the |0 basis state or the |1 basis state and thus regaining its similarity to a conventional bit. The actual state of the qubit after it has collapsed depends on the probabilities |a|2 and |b|2 immediately prior to the readout operation.
Superconducting Qubits
There are many different hardware and software approaches under consideration for use in quantum computers. One hardware approach uses integrated circuits formed of superconducting materials, such as aluminum or niobium. The technologies and processes involved in designing and fabricating superconducting integrated circuits are in some respects similar to those used for conventional integrated circuits.
Superconducting qubits are a type of superconducting device that can be included in a superconducting integrated circuit. Superconducting qubits can be separated into several categories depending on the physical property used to encode information. For example, they may be separated into charge, flux and phase devices, as discussed in, for example Makhlin et al., 2001, Reviews of Modern Physics 73, pp. 357-400. Charge devices store and manipulate information in the charge states of the device, where elementary charges consist of pairs of electrons called Cooper pairs. A Cooper pair has a charge of 2e and consists of two electrons bound together by, for example, a phonon interaction. See e.g., Nielsen and Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge (2000), pp. 343-345. Flux devices store information in a variable related to the magnetic flux through some part of the device. Phase devices store information in a variable related to the difference in superconducting phase between two regions of the phase device. Recently, hybrid devices using two or more of charge, flux and phase degrees of freedom have been developed. See e.g., U.S. Pat. No. 6,838,694 and U.S. patent application Ser. No. 2005-0082519.
Quantum Processor
A computer processor may take the form of an analog processor, for instance a quantum processor such as a superconducting quantum processor. A superconducting quantum processor may include a number of qubits and associated local bias devices, for instance two or more superconducting qubits.
A superconducting quantum processor may include a number of coupling devices operable to selectively couple respective pairs of qubits. Examples of superconducting coupling devices include rf-SQUIDs and dc-SQUIDs, which couple qubits together by flux. SQUIDs include a superconducting loop interrupted by one Josephson junction (an rf-SQUID) or two Josephson junctions (a dc-SQUID). The coupling devices may be capable of both ferromagnetic and anti-ferromagnetic coupling, depending on how the coupling device is being utilized within the interconnected topology. In the case of flux coupling, ferromagnetic coupling implies that parallel fluxes are energetically favorable and anti-ferromagnetic coupling implies that anti-parallel fluxes are energetically favorable. Alternatively, charge-based coupling devices may also be used. Other coupling devices can be found, for example, in U.S. patent application Ser. No. 11/247,857 and U.S. Provisional Patent Application No. 60/886,253. Respective coupling strengths of the coupling devices may be tuned between zero and a maximum value, for example, to provide ferromagnetic or anti-ferromagnetic coupling between qubits.
Regardless of the specific hardware being implemented, managing a single qubit requires control over a number of parameters. Conventionally, this requirement necessitated outside communication (that is, communication from outside of the processor architecture) with individual qubits. However, since overall processing power increases with the number of qubits in the system, high capacity processors that exceed the abilities of conventional supercomputers must manage a large number of qubits and thus the conventional approach of employing outside control over multiple parameters on individual qubits requires a complicated system for programming qubit parameters.
Thus, the scalability of quantum processors is limited by the complexity of the qubit parameter control system and there remains a need in the art for a scalable qubit parameter control system.
Computational Complexity Theory
In computer science, computational complexity theory is the branch of the theory of computation that studies the resources, or cost, of the computation required to solve a given computational problem. This cost is usually measured in terms of abstract parameters such as time and space, called computational resources. Time represents the number of steps required to solve a problem and space represents the quantity of information storage required or how much memory is required.
Computational complexity theory classifies computational problems into complexity classes. The number of complexity classes is ever changing, as new ones are defined and existing ones merge through the contributions of computer scientists. The complexity classes of decision problems include:                1. P—The complexity class containing decision problems that can be solved by a deterministic UTM using a polynomial amount of computation time;        2. NP (“Non-deterministic Polynomial time”)—The set of decision problems solvable in polynomial time on a non-deterministic UTM. Equivalently, it is the set of problems that can be “verified” by a deterministic UTM in polynomial time;        3. NP-hard (Nondeterministic Polynomial-time hard)—A problem H is in the class NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H. That is to say, L can be solved in polynomial time by an oracle machine with an oracle for H;        4. NP-complete—A decision problem C is NP-complete if it is complete for NP, meaning that:                    (a) it is in NP and            (b) it is NP-hard,                         i.e., every other problem in NP is reducible to it. “Reducible” means that for every problem L, there is a polynomial-time many-one reduction, a deterministic algorithm which transforms instances 1εL into instances cεC, such that the answer to c is YES if and only if the answer to 1 is YES. To prove that an NP problem A is in fact an NP-complete problem it is sufficient to show that an already known NP-complete problem reduces to A.        
Decision problems have binary outcomes. Problems in NP are computation problems for which there exists a polynomial time verification. That is, it takes no more than polynomial time (class P) in the size of the problem to verify a potential solution. It may take more than polynomial time, however, to find a potential solution. NP-hard problems are at least as hard as any problem in NP.
Optimization problems are problems for which one or more objective functions are minimized or maximized over a set of variables, sometimes subject to a set of constraints. For example, the Traveling Salesman Problem (“TSP”) is an optimization problem where an objective function representing, for example, distance or cost, must be optimized to find an itinerary, which is encoded in a set of variables representing the optimized solution to the problem. For example, given a list of locations, the problem may consist of finding the shortest route that visits all locations exactly once. Other examples of optimization problems include Maximum Independent Set, integer programming, constraint optimization, factoring, prediction modeling, and k-SAT. These problems are abstractions of many real-world optimization problems, such as operations research, financial portfolio selection, scheduling, supply management, circuit design, and travel route optimization. Many large-scale decision-based optimization problems are NP-hard. See e.g., “A High-Level Look at Optimization: Past, Present, and Future” e-Optimization.com, 2000.
Simulation problems typically deal with the simulation of one system by another system, usually over a period of time. For example, computer simulations can be made of business processes, ecological habitats, protein folding, molecular ground states, quantum systems, and the like. Such problems often include many different entities with complex inter-relationships and behavioral rules. In Feynman it was suggested that a quantum system could be used to simulate some physical systems more efficiently than a UTM.
Many optimization and simulation problems are not solvable using UTMs. Because of this limitation, there is need in the art for computational devices capable of solving computational problems beyond the scope of UTMs. In the field of protein folding, for example, grid computing systems and supercomputers have been used to try to simulate large protein systems. See Shirts et al., 2000, Science 290, pp. 1903-1904, and Allen et al, 2001, IBM Systems Journal 40, p. 310. The NEOS solver is an online network solver for optimization problems, where a user submits an optimization problem, selects an algorithm to solve it, and then a central server directs the problem to a computer in the network capable of running the selected algorithm. See e.g., Dolan et al, 2002, SIAM News Vol. 35, p. 6. Other digital computer-based systems and methods for solving optimization problems can be found, for example, in Fourer et al., 2001, Interfaces 31, pp. 130-150. All these methods are limited, however, by the fact they utilize digital computers, which are UTMs, and accordingly, are subject to the limits of classical computing that impose unfavorable scaling between problem size and solution time.
Graph Embedding
Graphs are an effective way of representing relationships among entities, and are commonly used in areas such as economics, mathematics, natural sciences and social sciences. While some graphs are simply used as a visual aid, others can be used to represent a problem to be solved. In fact, mapping a problem into graph format can sometimes help solve the problem. Instances of such problems include stock portfolio selection, microwave tower placement, delivery route optimization and other large-scale problems. Quantum computers can be used to solve such problems by way of translation of the original problem to a form that the quantum computer can solve. One method of doing this is through graph embedding, where a graph composed of a set of vertices and a set of edges that connect various vertices, representing a problem to be solved, is mapped into the qubit structure of a quantum processor and then solved.
Graph embedding is defining a particular drawing of a graph by mapping every node, or vertex, to a point on a plane and every edge to a straight or curved line that connects two nodes. This drawing is not unique, as there can be many permutations of the same graph. The number of ways a graph can be embedded depends on the characteristics and rules of the grid system upon which they are drawn. For example, one grid system can be a two-dimensional lattice. The edges may, for example, be constrained to be in two mutually orthogonal directions (e.g., up-down or left-right). Such a grid system has a connectivity of 4, meaning that each node can have at maximum four edges connected to it, the edges going only in the directions mentioned above. A similar grid system wherein edges can also extend diagonally (e.g., at 45°) and where they can cross is of connectivity 8. One form of graph embedding involves taking a graph drawn on one grid system and drawing an equivalent graph on another grid system.
Graphs that can be embedded can be broken into two types: planar and non-planar. Planar graphs are graphs that can be embedded on a two-dimensional plane such that no two edges intersect. A non-planar graph is a graph where at least two edges intersect. Some forms of graph embedding involve embedding a planar graph into a non-planar graph or attempting to make a non-planar graph as planar as possible, i.e., by reducing the number of intersections. However, some non-planar graphs cannot be embedded into a planar graph. The most famous examples of such graphs are the graphs K5 and K(3, 3). More information on non-planar graphs and their embeddings can be found in Boyer et al., 2004, Journal of Graph Algorithms and Applications 8, pp. 241-273.
One way of characterizing graph embeddings is their “efficiency”, that is, the amount of resources (e.g., vertices and edges), area, and path lengths that an embedding uses. An efficient graph embedding uses fewer resources, has less area, has lower average path lengths, or any combination thereof between vertices than an inefficient graph embedding. Since the same graph can be embedded in more than one way, it is preferred to find the most efficient embedding possible. Finding the most efficient graph is also known as graph optimization.
For small graphs, finding the most efficient graph embedding might be quite easy and might be performed on a conventional processor in a reasonable amount of time. However, when the graph has a substantial number of vertices and edges, finding the most efficient graph embedding becomes a complex computational task. Several techniques have been developed to find an efficient graph embedding, such as that developed by Gutwenger et al., 2002, Lecture Notes in Computer Science 2269, pp. 307-323. The Automated Graph Drawing (AGD) software program described in that publication is capable of mapping and compacting graphs using a variety of different techniques. However, all these techniques rely on the planarization of the original graph, which means the original graph is redrawn to have as few, if any, crossings as possible. This comes at the expense of having longer edge lengths and greater surface area, since non-planar graphs are generally more compact.
Other forms of graph embedding are discussed in Mutzel, 2002, Handbook of Applied Optimization, Oxford University Press, New York, 2002, pp. 967-977. Mutzel describes many different methodologies for graph embedding and optimization, but again all concentrate on making the graph as planar as possible. Part of the reason Mutzel desires planarity is that it is aesthetically better. However, in instances where aesthetics is not an important aspect of graph optimization, the techniques outlined by Mutzel would not produce the most efficient graph embedding.
Graph embedding is also used in the field of very large scale integration (VLSI) chip design. Given an electronic circuit with many different elements that need to be wired together in a limited space and with specific design rules to be followed, finding an efficient wiring scheme is a form of graph embedding. Examples of applying graph embedding techniques to VLSI design can be found in Shields et al., 2001, Parallel and Distributed Computing and Systems Conference, Anaheim, Calif.; and Heckmann et al., 1991, Proc. 17th Int. Workshop on Graph-Theoretic Concepts in Comp. Sci., pp. 25-35. However, techniques for efficient wiring in chips are limited by the design rules and thus are usually not extendable to general forms of graph embedding.
A technique of graph embedding into a lattice of qubits is described in Knysh et al., 2005, arXiv.org:quant-ph/0511131. Knysh describes a technique of mapping NP-complete problems into a lattice of qubits and performing adiabatic quantum computation to solve the problem. However, Knysh uses constant couplings between qubits and only nearest neighbor couplings, both of which reduce the flexibility and efficiency of the embedding and subsequent computation.
State of the Art
Many entities employ relational databases to store information. The information may be related to almost any aspect of business, government or individuals. For example, the information may be related to human resources, transportation, order placement or picking, warehousing, distribution, budgeting, oil exploration, surveying, polling, images, geographic maps, network topologies, identification, and/or security.
A relational database stores a set of “relations” or “relationships.” A relation is a two-dimensional table. The columns of the table are called attributes and the rows of the table store instances or “tuples” of the relation. A tuple has one element for each attribute of the relation. The schema of the relation consists of the name of the relation and the names and data types of all attributes. Typically, many such relations are stored in the database with any given relation having perhaps millions of tuples.
Searching databases typically employs the preparation of one or more queries. One common way of formatting queries is through Structured Query Language (SQL). QL-99 is the most recent standard, however many database vendors offer slightly different dialects or extensions of this standard. The basic query mechanism in SQL is the statement: SELECT L FROM R WHERE C, in which L identifies a list of columns in the relation(s) R, C is a condition that evaluates to TRUE, FALSE or UNKNOWN. Typically, only tuples that evaluate to TRUE are returned. Other query languages are also known, for example DATALOG, which may be particularly useful for recursive queries. Those of skill in the art will appreciate that while SQL or DATALOG are occasionally referred to herein, reference to a particular query language is for illustrative purposes only, and the present systems, methods and articles may be employed using any query language. Traditional querying or searching of databases presents a number of problems. Boolean matching is particularly onerous and unforgiving. Hence, searchers must specify a query that will locate the desired piece of information, without locating too much undesired information. Overly constrained queries will have no exact answer. Queries with insufficient constraints will have too many answers to be useful. Thus, the searcher must correctly constrain the query, with a suitable number of correctly selected constraints.
A common approach only identifies information that exactly corresponds to the constraints of the query. Another approach allows for inexact matches to some constraints. For example, the use of a wildcard character may be employed to locate variations of words being used in a query, for instance to capture both singular and plural occurrences of the word in the database. These approaches prove unsatisfactory in many situations. For example, it is common to have to reformulate a query numerous times before the results include the desired information, without including too much information. Often, it is not possible to form a satisfactory query that captures the desired information without capturing too much undesired information.
A further approach employs “fuzzy” matching capability. Such an approach typically replaces Boolean constraints with fuzzy counterparts. Thus, all tuples in the fuzzy or probabilistic database are directly or indirectly annotated with a number giving the probability or fuzziness level of the particular fact or piece of information. This approach disadvantageously requires the storage of a substantial amount of additional information.
These problems limit the usefulness of databases. This may particularly be a problem where queries are directed toward extracting useful knowledge from a large database of facts or other information.